package com.wp.dataStructure;

/**
 * Created by 王萍 on 2017/3/6 0006.
 */
public class 线性递归和尾递归 {

    //尾递归概念  http://www.ruanyifeng.com/blog/2015/04/tail-call.html

    //线性递归改为尾递归，   主要是把所有用到的内部变量改写成函数的参数

    //尾递归将每次每一次函数的调用转换为另一种同函数不同参数的调用，并结束上次函数的调用，
    // 而不会像线性递归那样在每次递归调用时，递归函数中的参数，局部变量等都要保存在栈中，可能会栈溢出。


    public static void main(String[] args) {

        System.out.println(fact(3));
        System.out.println(fact2(3, 1));

        // 斐波那契数列  1、1、2、3、5、8、13.......
        System.out.println(fibona(4));
        System.out.println(fibona2(4,0,1));
    }

    //线性递归求阶乘
    public static int fact(int n) {
        if (n < 0) {
            return 0;
        } else if (n == 0 || n == 1) {
            return 1;
        } else return n * fact(n - 1);
    }

    //尾递归求阶乘
    public static int fact2(int n, int a) {
        if (n < 0) {
            return 0;
        } else if (n == 0) {
            return 1;
        } else if (n == 1) {
            return a;
        } else return fact2(n - 1, a * n);
    }

    //线性递归求斐波那契数列
    public static int fibona(int n) {
        if (n < 2) {
            return n;
        } else return fibona(n - 1) + fibona(n - 2);
    }

    //尾递归求斐波那契数列
    public static int fibona2(int n, int acc1, int acc2) {
        if (n == 0) {
            return acc1;
        } else return fibona2(n - 1, acc2, acc1 + acc2);
    }


}
